It is often desirable to encrypt and decrypt data stored on a host computer (herein denoted as a “host”) via symmetric cryptography utilizing a secret key stored on a remote device, herein denoted as a “token”, without revealing the secret key to the host. Preferably, the token is a secure hardware device, ideally having the property that information stored thereon is physically protected from attack. A non-limiting example of a token is a smartcard. Thus, when the token is disconnected and removed from the host, the encrypted data on the host cannot be decrypted until the token is reconnected to the host. Because symmetric cryptography is employed, as noted above, the key used for decryption is the same as the key used for encryption.
Performing encryption and decryption in the above-described manner is referred to as “remotely-keyed encryption”, and is disclosed in U.S. Pat. No. 5,696,823 to Blaze, hereinafter denoted as “Blaze”.
The primary goal of Blaze is maintaining a high bandwidth for encryption/decryption while protecting the secret key in the token. For Blaze, a token provides adequate security but has insufficient bandwidth (i.e., limited processing and computational power). A host provides sufficient bandwidth (i.e., high processing and computational power), but lacks the security of the token. Blaze teaches a method by which the secret key in the token can be used by the host without revealing the key itself to the host, and in a manner that requires only limited overhead support from the token.
Prior Art Encryption
FIG. 1 conceptually illustrates the prior-art remotely-keyed encryption method of Blaze. A host 101 and a token 103 communicate via a channel 100, which can be a smartcard interface for a smartcard token 103. Plaintext data 107 of size m resides on host 101, and a secret key K 105 resides on token 103. The method of Blaze allows host 101 to encrypt plaintext data 107 without directly requiring secret key 105, and requiring only minimal communication with token 103 and processing thereby.
First, host 101 breaks plaintext data 107 into n plaintext blocks 109, P1, P2, . . . Pn, each of size h, in preparation for encryption by a block cipher. It is noted that structurally, Blaze requires that plaintext data 107 be broken into such blocks, and that a block cipher be utilized. A consequence of this is that, in general, the total size of plaintext blocks 109 is greater than that of original plaintext data 107. Unless m happens to be an integer multiple of block size b (which in general will not be the case), nb>m. As a further consequence, the size of resulting ciphertext data 131 will also be larger than that of original plaintext data 107. This is an important restriction on the prior art for certain applications, and is discussed further, below.
Host 101 then combines plaintext blocks P2 through Pn with a hash of plaintext block P1 via an exclusive-OR (XOR) operation, wherein the hash is computed by host 101 using a secure hash function 111. This operation results in intermediate blocks 113 denoted as I2 through In. The concatenation of intermediate blocks 113 is input by host 101 to hash function 111 for an XOR operation with plaintext block P1 to produce an intermediate block I1 115. In a transmission 117, host 101 sends block I1 115 to token 103. Transmission 117 is the only transmission from host 101 to token 103 in the Blaze encryption method.
When token 103 receives intermediate block I1 115, secret key 105 is used to encrypt intermediate block I1 115 via an encryption function EK 119, the result of which is a ciphertext block C1 121. Immediately thereafter, token 103 uses secret key 105 to encrypt ciphertext block C1 121 via encryption function EK 119, the result of which is a derivative key KP 123. Then, in a transmission 125, token 103 sends both ciphertext block C1 121 and derivative key KP 123 to host 101. Transmission 125 is the only transmission from token 103 to host 101 in the Blaze encryption method. It is emphasized, however, that in transmission 125, two data items are sent from token 103 to host 101.
Following transmission 125 from token 103 to host 101, the remaining steps of the encryption according to Blaze are carried out entirely by host 101.
Host 101 uses derivative key KP 123 to encrypt each of intermediate blocks I2 through In 113 via a block encryption function EKP 127, the results of which are ciphertext blocks C2 through Cn 129. When prefixed with ciphertext block C1 121, the concatenation produces ciphertext data 131.
Reviewing the above prior-art encryption method, it is pointed out that communication between host 101 and token 103 is minimal, involving only transmission 117 and transmission 125, in which only three data objects (I1, C1, and KP) are transmitted. Furthermore, the processing overhead on token 103 is also minimal, involving only two encryption operations using secret key K 105. The bulk of the processing is performed by host 101, and moreover, secret key K 105 remains on token 103 and is never revealed to host 101. Thus, host 101 is incapable of performing the encryption without token 103. Specifically, without a connection to token 103, host 101 is incapable of performing a second encryption of a second plaintext data even after having performed the above encryption on the first plaintext data. The foregoing are the objectives of the prior-art Blaze encryption method.
Prior Art Decryption
FIG. 2 conceptually illustrates the prior-art remotely-keyed decryption method of Blaze, whose steps are the reverse of the encryption method illustrated in FIG. 1. Starting with a block of ciphertext data 201, whose size is nb, host 101 breaks ciphertext data 201 into n blocks: a block C1 203 and blocks C2 through Cn 205. In a transmission 207, host 101 transmits ciphertext block C1 203 to token 103. Transmission 207 is the only transmission from host 101 to token 103 in the Blaze decryption method.
Token 103 uses secret key K 105 as input to a decryption function 219 to derive an intermediate block I1 209 from ciphertext block C1 203, which is the complementary operation of that illustrated in FIG. 1 (using secret key K 105 as input to encryption function EK 119 on block I1 115 to obtain ciphertext block C1 121). In addition, token 103 uses secret key K 105 as input to encryption function EK 119 to obtain a derivative key KP 223 from ciphertext block C1 203, which is a similar operation of that illustrated in FIG. 1 (using secret key K 105 as input to encryption function EK 119 to obtain derivative key KP 123 from ciphertext block C1 121). Then, in a transmission 225, token 103 sends both intermediate block I1 209 and derivative key KP 223 to host 101. Transmission 225 is the only transmission from token 103 to host 101 in the Blaze decryption method. It is emphasized, however, that in transmission 225, two data items are sent from token 103 to host 101.
Following transmission 225 from token 103 to host 101, the remaining steps of the decryption according to Blaze are carried out entirely by host 101.
Using a derivative key KP 223 as input to a decryption function DKP 227, host 101 obtains intermediate blocks I2 through In 213 from ciphertext blocks C2 through Cn 205. This is the complementary operation of that illustrated in FIG. 1 (using derivative key KP 123 with encryption function EKP 127 to obtain ciphertext blocks C2 through Cn 121 from intermediate blocks I2 through In 113).
Next, host 101 uses intermediate blocks I2 through In 213 as input to hash function 111 for the XOR that derives a plaintext block P1 from intermediate block I1 209. Referring to FIG. 1, it is seen that this is complementary to the similar step of obtaining intermediate block I1 115 from block P1 of plaintext blocks 109, because the XOR operation is bidirectionally symmetrical.
Then host 101 inputs plaintext block P1 into hash function 111 and performs the XOR operation that completes the transformation of I2 through In 213 into plaintext blocks P2 through Pn for concatenation with plaintext block P1 to obtain plaintext blocks P1 through Pn 209, which then yield plaintext data 231 to complete the decryption process.
Likewise reviewing the above prior-art decryption method, it is pointed out that communication between host 101 and token 103 is minimal, involving only transmission 207 and transmission 225, in which only three data objects (C1, I1, and KP) are transmitted. Furthermore, the processing overhead on token 103 is also minimal, involving only one encryption operation and one decryption operation using secret key K 105. The bulk of the processing is performed by host 101, and moreover, secret key K 105 remains on token 103 and is never revealed to host 101. Thus, host 101 is incapable of performing the decryption without token 103. Specifically, without a connection to token 103, host 101 is incapable of performing a second decryption of a second ciphertext data even after having performed the above decryption on the first ciphertext data. The foregoing are the objectives of the prior-art Blaze encryption method.
It is pointed out however, that the size of plaintext data 231 (FIG. 2) is necessarily a multiple of the block size b, whereas the size of plaintext data 107 (FIG. 1) is in general not a multiple of a block size.
Restrictions of the Prior Art
Although Blaze achieves its goals, there are restrictions on the prior art which preclude utilization in an important area of Digital Rights Management, as detailed below. The restriction is associated with the fact that ciphertext data typically has a larger size than the equivalent plaintext, as previously discussed. In practical terms, the expansion of plaintext data 107 (of size m) into plaintext blocks 109 (of size nb>m generally) is typically facilitated by padding plaintext data 107 to a size of nb.
The expansion of the ciphertext, as noted above, is problematical in certain applications, as detailed below. In addition to the expansion of the ciphertext, the use of padding can lead to further problems under certain circumstances, because such padding may have to be removed after decryption from ciphertext data 131, and additional information must therefore be provided to enable the correct removal of the padding.
Special Digital Rights Management Requirement
Digital Rights Management (hereinafter referred to as “DRM”) concerns administering and enforcing usage restrictions on proprietary digital material, such as executable computer programs and digital content, including data and multimedia material.
Cryptographic techniques are important tools for DRM, but there is often an additional special requirement on encryption/decryption, because the plaintext of the data to be encrypted may reside in an allocated area of data storage, wherein the ciphertext after encryption is to be interchanged, or substituted for the plaintext. That is, the ciphertext must be able to reside within the same pre-allocated storage area as originally occupied by the plaintext, and vice-versa. In these DRM applications, the size of the ciphertext must therefore not exceed that of the plaintext. In order to obtain the highest security levels for such applications, the ciphertext must be exactly the same size as the plaintext. This is a special requirement, which is not supported by the prior art.
In a non-limiting example of this special requirement, a DRM application involves protecting portions of the executable code of a piece of computer software. DRM for such an application is often denoted as “Software Rights Management” or “SRM”. In typical cases, one or more modules of the computer software are encrypted, and thus cannot be executed until the ciphertext thereof is replaced by the decrypted plaintext. For this to function properly without affecting the operation of other modules in the software, the above-described special requirement is necessary: the ciphertext after encryption must be exactly the same size as the plaintext.
It can thus be seen that the prior-art method of Blaze is generally inadequate for this special requirement because Blaze necessitates breaking the plaintext into equal-sized blocks (wherein each block has a plurality of bits), deriving intermediate results therefrom, and finally using a block cipher to encrypt each block separately. Unless the size of the plaintext happens to be an exact multiple of the block size (which in general is not the case), Blaze requires that the plaintext be extended (e.g., through padding) to the nearest multiple of the block size before encryption. The ciphertext of Blaze is therefore in general larger than the original (non-padded) plaintext, and does not meet the additional requirement described above.
There is thus a need for, and it would be highly advantageous to have, a method for efficient remotely-keyed cryptography, wherein the size of the ciphertext does not exceed the size of the plaintext. This goal is met by the present invention.